Searching is a function in research communities of computational geometry and machine learning. In particular, searching plays an important role in many applications for computer vision. Computer vision deals with computational understanding and use of information present in visual images. Computer vision has adopted a searching pattern known as a nearest neighbor (NN) search. The NN search finds points that are closest to a query point. The NN search is adapted for fast matching to establish correspondences of local points between two images, such as wide-baseline matching for 3D modeling from photo databases and panorama building. Furthermore, the NN search technique is used for fast indexing and searching of large databases, such as content-based image and video retrieval.
A problem with the NN search occurs when using a conventional k-dimensional (kd)-tree. The kd-tree is a space-partitioning data structure for organizing points in a k-dimensional space. The conventional kd-tree has nodes that contain data and links to other nodes. The NN search requires a descent down the conventional kd-tree to a leaf node to obtain a first candidate. However, because of the structure of a conventional kd-tree, this first candidate may not be the nearest neighbor to the input point.
As the popularity of computer vision applications continues to grow, there is an increasing opportunity to find a nearest neighbor efficiently in large-scale vision applications.